//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "iterator.h"
#include "char_traits.h"
#include "string_utils.h"
#include "hash.h"
#include "search.h"
#include "forward.h"

FC_NAMESPACE_BEGIN


template <class T>
class basic_string_ref
{
public:
	typedef size_t								size_type;
	typedef T									value_type;
	typedef T*									pointer;
	typedef const T*							const_pointer;
	typedef T&									reference;
	typedef const T&							const_reference;
	typedef T*									iterator;
	typedef const T*							const_iterator;
	typedef fc::reverse_iterator<iterator>		reverse_iterator;
	typedef fc::reverse_iterator<const_iterator> const_reverse_iterator;
	typedef ptrdiff_t							difference_type;
	typedef basic_string_ref<T>					this_type;
	typedef char_traits<T>						traits_type;

	static const size_type npos = size_type(-1);
	static const size_type maxsize = size_type(-2);

	basic_string_ref()
		: m_begin(0), m_end(0)
		{
		}

	basic_string_ref( const T* s, size_t n )
		: m_begin(s), m_end(s + n)
		{
		}

	basic_string_ref( const T* s )
		: m_begin(s), m_end(s + traits_type::length(s))
		{
		}

	basic_string_ref( const this_type& str )
		: m_begin(str.m_begin), m_end(str.m_end)
		{
		}

	basic_string_ref( const this_type& str, size_t pos, size_t n = npos )
		: m_begin(0), m_end(0)
		{
			m_begin = str.m_begin + pos;
			m_end = (n == npos ? str.m_end : str.m_begin + pos + n);
		}

	basic_string_ref( const_iterator first, const_iterator last )
		: m_begin(first), m_end(last)
		{
		}

	bool empty() const		{ return m_begin == m_end; }
	size_t size() const		{ return size_t(m_end - m_begin); }
	size_t length() const	{ return size_t(m_end - m_begin); }

	reference		operator [] ( size_t i )		{ return m_begin[i]; }
	const_reference operator [] ( size_t i ) const	{ return m_begin[i]; }
	reference at( size_t i ) { FC_ASSERT(i < size()); return m_begin[i]; }
	const_reference at( size_t i ) const { FC_ASSERT(i < size()); return m_begin[i]; }

	reference		front()			{ return *m_begin; }
	const_reference front() const	{ return *m_begin; }
	reference		back()			{ return *(m_end - 1); }
	const_reference back()	const	{ return *(m_end - 1); }
	iterator		begin()			{ return m_begin; }
	const_iterator	begin() const	{ return m_begin; }
	iterator		end()			{ return m_end; }
	const_iterator	end() const		{ return m_end; }
	reverse_iterator		rbegin()		{ return reverse_iterator(m_end); }
	const_reverse_iterator	rbegin() const	{ return const_reverse_iterator(m_end); }
	reverse_iterator		rend()			{ return reverse_iterator(m_begin); }
	const_reverse_iterator	rend() const	{ return const_reverse_iterator(m_begin); }

	pointer			data()			{ return m_begin; }
	const_pointer	data() const	{ return m_begin; }
	const_pointer	c_str() const	{ return m_begin; }

	void remove_prefix( size_t n ) { FC_ASSERT(n <= size_t(m_end - m_begin)); m_begin += n; }
	void remove_suffix( size_t n ) { FC_ASSERT(n <= size_t(m_end - m_begin)); m_end -= n; }
	void pop_front() { remove_prefix(1); }
	void pop_back() { remove_suffix(1); }

	void swap( this_type& x )
	{
		fc::swap( m_begin, x.m_begin );
		fc::swap( m_end, x.m_end );
	}

	this_type& operator =( const this_type& str )	{ return assign( str.begin(), str.end() ); }
	this_type& operator =( const T* s )				{ return assign( s, s + traits_type::length(s) ); }

	this_type& assign( const T* s, size_t n )		{ return assign( s, s + n ); }
	this_type& assign( const T* s )					{ return assign( s, s + traits_type::length(s) ); }
	this_type& assign( const this_type& str )		{ return assign( str.m_begin, str.m_end ); }
	this_type& assign( const this_type& str, size_t pos, size_t n ) { return assign( str.m_begin + pos, str.m_begin + pos + n ); }
	this_type& assign( const_iterator first, const_iterator last )
	{
		m_begin = (T*)first;
		m_end = (T*)last;
		return *this;
	}

	void clear() { m_end = m_begin; }

	size_t find( const this_type& str, size_t pos = 0 ) const { return find( str.c_str(), pos, str.size() ); }
	size_t find( const T* s, size_t pos = 0 ) const { return find( s, pos, traits_type::length(s) ); }
	size_t find( const T* s, size_t pos, size_t n ) const
	{
		if( FC_LIKELY(pos < size_type(m_end - m_begin)) )
		{
			if( FC_UNLIKELY(!n) )
				return pos;

			// simply using the search algorithm here seems to be the most consistent.
			const T* const it = fc::search( m_begin + pos, m_end, s, s + n );
			if( it != m_end )
				return size_type(it - m_begin);
/*
			const_iterator last = m_end;
			for( const_iterator first = m_begin + pos; first < last; ++first )
			{
#if 0
				// find next match of range to search.
				first = (const_iterator)fc::find( first, last, *s );
				if( first == last )
					break; // no match

				const T* first1 = first;
				const T* first2 = s;
				size_t i = n;

				do {
					++first1;
					++first2;
				} while( --i && *first1 == *first2 );

				if( !i )
					return size_type(first - m_begin);
#else
				// find next match of range to search.
				first = (const_iterator)traits_type::find( first, size_t(last - first), *s );
				if( !first )
					break; // no match

				if( traits_type::compare(first, s, n) == 0 )
					return size_type(first - m_begin);
#endif
			}
			*/
		}

		return npos;
	}

	size_t find( T c, size_t pos = 0 ) const
	{
		if( FC_LIKELY(pos < size_type(m_end - m_begin)) )
		{
			const_iterator first = m_begin + pos;
			const_iterator it = traits_type::find( first, size_type(m_end - first), c );
			if( it != 0 )
				return size_type(it - m_begin);
		}

		return npos;
	}

	size_t rfind( const this_type& str, size_t pos = npos ) const { return rfind( str.c_str(), pos, str.size() ); }
	size_t rfind( const T* s, size_t pos = npos ) const { return rfind( s, pos, traits_type::length(s) ); }
	size_t rfind( const T* s, size_t pos, size_t n ) const
	{
		const size_t thisSize = size_t(m_end - m_begin);
		const_iterator first = m_begin;
		const_iterator last = m_begin + (fc::min(thisSize - n, pos) + n);

		if( FC_LIKELY(n < thisSize) )
		{
			// if !n then we cannot return npos.
			if( FC_UNLIKELY(n == 0) )
				return fc::min( thisSize, pos );

			while( first < last )
				if( *--last == *s && traits_type::compare( last, s, n ) == 0 )
					return size_t(last - m_begin);
		}

		return npos;
	}

	size_t rfind( T c, size_t pos = npos ) const
	{
		const size_t thisSize = size_t(m_end - m_begin);
		if( FC_LIKELY(thisSize > 0) )
		{
			const_iterator first = m_begin;
			const_iterator last = m_begin + (fc::min(thisSize - 1, pos) + 1);

			while( first != last )
				if( *--last == c )
					return size_t(last - first);
		}

		return npos;
	}

	size_t find_first_of( const this_type& str, size_t pos = 0 ) const { return find_first_of( str.m_begin, pos, str.size() ); }
	size_t find_first_of( const T* s, size_t pos = 0 ) const { return find_first_of( s, pos, traits_type::length(s) ); }
	size_t find_first_of( const T* s, size_t pos, size_t n ) const
	{

#if 0 //using traits_type
		if( FC_LIKELY(n && pos < size_type(m_end - m_begin)) )
		{
			const T* const last = m_end;
			for( const T* first = m_begin + pos; first < last; ++first )
				if( traits_type::find(s, n, *first) != 0 )
					return size_type(first - m_begin);
		}

#else
		if( FC_LIKELY(pos < size_type(m_end - m_begin)) )
		{
			const T* const it = fc::find_first_of( m_begin + pos, m_end, s, s + n );
			if( it != m_end )
				return size_type(it - m_begin);
		}
#endif

		return npos;
	}

	size_t find_first_of( T c, size_t pos = 0 ) const
	{
		return find( c, pos );
	}


	size_t find_first_not_of( const this_type& str, size_t pos = 0 ) const { return find_first_not_of( str.c_str(), pos, str.size() ); }
	size_t find_first_not_of( const T* s, size_t pos = 0 ) const { return find_first_not_of( s, pos, traits_type::length(s) ); }
	size_t find_first_not_of( const T* s, size_t pos, size_t n ) const
	{
		if( FC_LIKELY(pos < size_type(m_end - m_begin)) )
		{
			const_iterator it = fc::find_first_not_of( m_begin + pos, m_end, s, s + n );
			if( it != m_end )
				return size_type(it - m_begin);
		}

		return npos;
	}

	size_t find_first_not_of( T c, size_t pos = 0 ) const
	{
		for( iterator it = m_begin + pos; it < m_end; ++it )
			if( *it != c )
				return size_t(it - m_begin);

		return npos;
	}

	size_t find_last_of( const this_type& str, size_t pos = npos ) const { return find_last_of( str.m_begin, pos, str.size() ); }
	size_t find_last_of( const T* s, size_t pos = npos ) const { return find_last_of( s, pos, traits_type::length(s) ); }
	size_t find_last_of( const T* s, size_t pos, size_t n ) const
	{
		if( FC_LIKELY(size_type(m_end - m_begin) && pos) )
		{
			const_iterator first = m_begin;
			const_iterator last = m_begin + (fc::min(size_t(m_end - m_begin) - n, pos) + n);
			const_iterator it = fc::find_last_of( first, last, s, s + n );
			if( it != m_end )
				return size_type(it - m_begin);
		}

		return npos;
	}

	size_t find_last_of( T c, size_t pos = npos ) const
	{
		return rfind( c, pos );
	}

	size_t find_last_not_of( const this_type& str, size_t pos = npos ) const { return find_last_not_of( str.c_str(), pos, str.size() ); }
	size_t find_last_not_of( const T* s, size_t pos = npos ) const { return find_last_not_of( s, pos, traits_type::length(s) ); }
	size_t find_last_not_of( const T* s, size_t pos, size_t n ) const
	{
		if( FC_LIKELY(size_type(m_end - m_begin) && pos) )
		{
			const_iterator first = m_begin;
			const_iterator last = m_begin + (fc::min(size_t(m_end - m_begin) - n, pos) + n);
			const_iterator it = fc::find_last_not_of( first, last, s, s + n );
			if( it != m_end )
				return size_type(it - m_begin);
		}

		return npos;
	}

	size_t find_last_not_of( T c, size_t pos = npos ) const
	{
		const_iterator first = m_begin, last = m_begin + fc::min(size() - 1, pos) + 1;
		while( last != first )
			if( *--last != c )
				return size_t(last - first);

		return npos;
	}

	this_type substr( size_t pos = 0, size_t n = npos ) const
	{
		iterator first = m_begin + pos;
		iterator last = (n == npos ? m_end : first + n);
		return this_type(first, last);
	}

	this_type substr( const_iterator first, const_iterator last ) const
	{
		return this_type(first, last);
	}

	int compare( const T* s ) const { return compare( m_begin, m_end, s, s + traits_type::length(s) ); }
	int compare( const T* s, size_t n ) const { return compare( m_begin, m_end, s, n ); }
	int compare( size_t pos, size_t n, const T* s ) const { return compare( m_begin + pos, m_begin + pos + n, s, s + traits_type::length(s) ); }
	int compare( size_t pos, size_t n, const T* s, size_t len ) const { return compare( m_begin + pos, m_begin + pos + n, s, s + len ); }
	int compare( const this_type& str ) const { return compare( m_begin, m_end, str.m_begin, str.m_end ); }
	int compare( size_t pos, size_t n, const this_type& str ) const
	{
		return compare( m_begin + pos, m_begin + pos + fc::min(n, size_t(m_end - m_begin) - pos),
			str.m_begin, str.m_end );
	}

	int compare( size_t pos, size_t n, const this_type& str, size_t pos2, size_t n2 ) const
	{
		return compare( m_begin + pos, m_begin + pos + n,
			str.m_begin + pos2, str.m_begin + pos2 + n2 );
	}

	static int compare( const T* a, const T* b )
	{
		return compare( a, a + traits_type::length(a), b, b + traits_type::length(b) );
	}

	static int compare( const T* first1, const T* last1, const T* first2, const T* last2 )
	{
		FC_ASSERT(first1 <= last1 && first2 <= last2);
		size_t d1 = size_t(last1 - first1);
		size_t d2 = size_t(last2 - first2);
		size_t n = fc::min( d1, d2 );

		int ret = traits_type::compare( first1, first2, n );
		if( ret == 0 && d1 != d2 )
			ret = (d1 < d2 ? -1 : 1);

		return ret;
	}

	this_type& make_upper() { fc::make_upper( m_begin, m_end ); return *this; }
	this_type& make_upper( size_t pos, size_t n ) { fc::make_upper( m_begin + pos, m_begin + pos + n ); return *this; }

	this_type& make_lower() { fc::make_lower( m_begin, m_end ); return *this; }
	this_type& make_lower( size_t pos, size_t n ) { fc::make_lower( m_begin + pos, m_begin + pos + n ); return *this; }

	int to_int() const { return fc::to_int( m_begin, size_t(0) ); }
	float to_float() const { return fc::to_float( m_begin, size_t(0) ); }
	double to_double() const { return fc::to_double( m_begin, size_t(0) ); }

	bool iterator_is_valid( const_iterator it ) const
	{
		return (it >= m_begin && it <= m_end);
	}

	size_t get_hash() const
	{
		return fnv_hash( m_begin, size() );
	}

protected:
	// this allows derived classes to inline simple function calls.
	template <class CharT, class Alloc> friend class basic_string;
	template <class CharT, size_t N, class Alloc> friend class fixed_string;

	T* m_begin;
	T* m_end;
};

//template <class T> T basic_string_ref<T>::_globalEmptyString = 0;



// global operators

template <class T> inline
	void swap( basic_string_ref<T>& a, basic_string_ref<T>& b )
	{
		a.swap(b);
	}

template <class T> inline
	bool operator ==( const basic_string_ref<T>& a, const basic_string_ref<T>& b )
	{
		return (a.size() == b.size() &&
			char_traits<T>::compare( a.c_str(), b.c_str(), a.size()) == 0);
	}

template <class T> inline
	bool operator !=( const basic_string_ref<T>& a, const basic_string_ref<T>& b )
	{
		return !(a == b);
	}

template <class T> inline
	bool operator ==( const basic_string_ref<T>& a, const T* s )
	{
		return a.compare(s) == 0;
	}

template <class T> inline
	bool operator !=( const basic_string_ref<T>& a, const T* s )
	{
		return !(a == s);
	}

template <class T> inline
	bool operator ==( const T* s, const basic_string_ref<T>& b )
	{
		return b.compare(s) == 0;
	}

template <class T> inline
	bool operator !=( const T* s, const basic_string_ref<T>& b )
	{
		return !(b == s);
	}

template <class T> inline
	bool operator <( const basic_string_ref<T>& a, const basic_string_ref<T>& b )
	{
		return a.compare(a.begin(), a.end(), b.begin(), b.end()) < 0;
	}

template <class T> inline
	bool operator <( const basic_string_ref<T>& a, const T* s )
	{
		return a.compare(s) < 0;
	}

template <class T> inline
	bool operator <( const T* s, const basic_string_ref<T>& b )
	{
		return b.compare(s) < 0;
	}

template <class T> inline
	bool operator >( const basic_string_ref<T>& a, const basic_string_ref<T>& b )
	{
		return b < a;
	}

template <class T> inline
	bool operator >( const basic_string_ref<T>& a, const T* s )
	{
		return s < a;
	}

template <class T> inline
	bool operator >( const T* s, const basic_string_ref<T>& b )
	{
		return b < s;
	}

template <class T> inline
	bool operator <=( const basic_string_ref<T>& a, const basic_string_ref<T>& b )
	{
		return !(b < a);
	}

template <class T> inline
	bool operator <=( const basic_string_ref<T>& a, const T* s )
	{
		return !(s < a);
	}

template <class T> inline
	bool operator <=( const T* s, const basic_string_ref<T>& b )
	{
		return !(b < s);
	}

template <class T> inline
	bool operator >=( const basic_string_ref<T>& a, const basic_string_ref<T>& b )
	{
		return !(a < b);
	}

template <class T> inline
	bool operator >=( const basic_string_ref<T>& a, const T* s )
	{
		return !(s < a);
	}

template <class T> inline
	bool operator >=( const T* s, const basic_string_ref<T>& b )
	{
		return !(s < b);
	}




FC_NAMESPACE_END

